//
// Created by Lenovo on 2024/3/2.
//
#include<bits/stdc++.h>
using namespace std;
//加油站
class Solution {
public:
    
    int curIndex,curGas;        //当前索引和当前油量
    
    bool judge(int startIndex,vector<int>& gas, vector<int>& cost){
        curIndex=startIndex;
        curGas=gas[startIndex];
        if(curGas<cost[curIndex]) return false;
        while(true){
            if(curGas>=cost[curIndex]){
                int costGas=cost[curIndex];
                curIndex=(curIndex+1)%gas.size();
                curGas=curGas-costGas+gas[curIndex];
                if(curIndex==startIndex) return true;
            }else{
                break;
            }
        }
        return false;
    }
    
    
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for(int i=0;i<gas.size();i++){
            bool flag = judge(i, gas, cost);
            if(flag) return i;
        }
        return -1;
    }

    //优化
    int canCompleteCircuit2(vector<int>& gas, vector<int>& cost) {
        int curSum=0;           //当前总油量
        int min = INT_MAX;      //从0处出发，邮箱里的油量的最小值
        for(int i=0;i<gas.size();i++){
            int rest=gas[i]-cost[i];    //每站带来的剩余油量
            curSum+=rest;
            if(curSum<min) min=curSum;
        }
        if(curSum<0) return -1;         //情况1，说明gas的总和小于cost的总和，无论如何都跑不完一圈
        if(min>=0) return 0;            //情况2，说明从0处出发任意时刻油量都是充足的，从0处可以跑完一圈
        //情况3，从后向前看，如果哪个节点能把min这个负数填平，该节点就可以为出发节点
        for(int i=gas.size()-1;i>=0;i--){
            int rest=gas[i]-cost[i];
            min+=rest;
            if(min>=0){
                return i;
            }
        }
        return -1;
    }
};